package dp;

import java.util.ArrayList;
import java.util.List;

public class P22 {
    public List<String> generateParenthesis(int n) {
        List<List<String>> totalList = new ArrayList<>(n);
        List<String> list = new ArrayList<>();
        list.add("()");
        totalList.add(new ArrayList<>(0));
        totalList.add(list);
        for (int i = 2; i <= n; i++) {
            List<String> sub = new ArrayList<>();
            for (int left = 0; left < i; left++) {
                int right = i - left - 1;
                List<String> leftList = totalList.get(left);
                List<String> rightList = totalList.get(right);
                if (leftList.size() == 0) {
                    for (String rightItem : rightList) {
                        sub.add("()" + rightItem);
                    }
                } else if (rightList.size() == 0) {
                    for (String leftItem : leftList) {
                        sub.add("(" + leftItem + ")");
                    }
                }
                for (String leftItem : leftList) {
                    for (String rightItem : rightList) {
                        sub.add("(" + leftItem + ")" + rightItem);
                    }
                }
            }
            totalList.add(sub);
        }
        return totalList.get(n);
    }

    public static void main(String[] args) {
        List<String> strings = new P22().generateParenthesis(4);
        System.out.println(strings);
        System.out.println("\n" +
                "[(((()))), ((()())), ((())()), ((()))(), (()(())), (()()()), (()())(), (())(()), (())()(), ()((())), ()(()()), ()(())(), ()()(()), ()()()()]");
    }
}
